package leetcode_900;

import java.util.Deque;
import java.util.LinkedList;

/**
 *@author 周杨
 *ShortestSubarrayWithSumAtLeastK_862_  给定一个正整数N 和一个数组 问数组里连续子数组和大于等于N的 最小长度
 *describe:用双边队列 滑动窗口法 AC 63%
 *2018年11月6日 上午10:36:45
 */
public class ShortestSubarrayWithSumAtLeastK_862_ {
	public static void main(String[] args) {
		ShortestSubarrayWithSumAtLeastK_862_ test=new ShortestSubarrayWithSumAtLeastK_862_();
		System.out.println(test.shortestSubarray(new int[] {2,-1,2}, 3));
	}
	
	
	public int shortestSubarray(int[] A, int K) {
		long []sum=new long[A.length+1];
		for(int i=0;i<A.length;++i)
			sum[i+1]=sum[i]+(long)A[i];
		//如果区间里出现负数 那么不可能结果是以这个负数结尾的区间 那么队列必须弹出它 因为它既占了长度 又减少了和
		int res=A.length+1;
		Deque<Integer> queue=new LinkedList<Integer>();//双边队列
		for(int i=0;i<sum.length;++i) {
			//如果该区间和小于队列上一个区间和 说明这个数是负数
			while(!queue.isEmpty()&&sum[i]<sum[queue.getLast()])
				queue.removeLast();//要删除队列尾的元素 直至队列里是递增的sum和
			while(!queue.isEmpty()&&sum[i]-sum[queue.getFirst()]>=K)
				res=Math.min(res, i-queue.removeFirst());
			//因为队列里的元素是递增的 那么最优解就从不断缩小这个窗口开始
			queue.offer(i);//会从0开始入队列 直到N
		}
		return res<=A.length?res:-1;
	}
	
	
	/**
	 * describe: 思想错误 因为会出现负数
	 * 2018年11月6日 上午9:51:26
	 */
	public int shortestSubarray1(int[] A, int K) {
        int sum=0;
        int res=A.length;
        int left=-1;//定义左边界
        for(int i=0;i<A.length;++i) {
        	sum+=A[i];
        	if(sum<K)
        		continue;
        	else{
        		res=Math.min(res, i-left);
        		while(left<i&&sum>=K) {
        			sum-=A[++left];
        			if(sum>=K) {
        				res=Math.min(res, i-left);
        			}
        		}
        	}
        }
        return res==A.length?-1:res;
    }
}
